Typically, temporal variations in video sequences occur due to camera or object motion. If compensation for this motion is available, improvement in the video image prediction sequences is also possible, with relatively compact motion information, which enables video compression algorithms to significantly reduce the amount of data needed to transmit the video sequences with an acceptable level of quality.
Under the international video coding standard H.264, MPEG-4 Part 10, or Advance Video Coding (AVC), the coding processes are performed using units of macroblocks of 16×16 pixels. In addition, motion compensation is typically performed by partitioning the macroblocks into square or rectangular sub-macroblocks in a quad-tree decomposition. In this motion compensation technique, each leaf level block of size N×N is associated with a different motion vector and coding mode. Moreover, the residual error is coded using an appropriate transform, followed by quantization and entropy coding.
Conventional techniques have yielded an improvement in the compensation of the camera or object motion over previous techniques. However, because the conventional quad-tree decomposition is restricted to macroblocks and sub-macroblocks of squares or rectangles, the shape of a macroblock typically does not correspond to the outline of the shape of the moving object. Because of the fixed shapes of the macro-blocks and sub-macroblocks, in situations where the same macroblock includes several regions with different motion, the coding efficiency is substantially reduced.